package xyf.p05.heap_trie;

import commons.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * ClassName: P0023_MergeK
 * Description:
 * Author: xyf
 * Date: 9/23/22 9:02 PM
 * Version: 1.0
 **/
public class P0023_MergeK
{
    public ListNode mergeKLists(ListNode[] lists)
    {
        if (lists == null || lists.length == 0)
        {
            return null;
        }
        PriorityQueue<ListNode> minQueue = new PriorityQueue<>(new Comparator<ListNode>()
        {
            @Override
            public int compare(ListNode o1, ListNode o2)
            {
                return o1.val - o2.val;
            }
        });

        for (int i = 0; i < lists.length; i++)
        {
            if (lists[i] != null)
            {
                minQueue.offer(lists[i]);
            }
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while (!minQueue.isEmpty())
        {
            ListNode tmp = minQueue.poll();
            cur.next = tmp;
            cur = cur.next;
            if (tmp.next != null)
            {
                minQueue.offer(tmp.next);
            }
        }
        return head.next;
    }
}